/*
    前缀和
    本质是动态规划
*/

// 一维前缀和

// #include <iostream>
// using namespace std;

// int main() 
// {
//     //1.输入
//     int n = 0, q = 0;
//     cin >> n >> q;
//     int arr[n];
//     for(int i = 0; i < n; i++) cin >> arr[i];

//     //2.前缀和
//     long long dp[n+1];
//     dp[0] = 0;
//     for(int i = 1; i <= n; i++) dp[i] = dp[i-1] + arr[i-1];
    
//     int l = 0, r = 0;
//     while(q--)
//     {
//         cin >> l >> r;
//         cout << dp[r] - dp[l-1] << endl;
//     }

//     return 0;
// }

// 二维前缀和
// #include <iostream>
// #include <vector>
// using namespace std;

// int main() 
// {
//     //1.输入
//     int n = 0, m = 0, q = 0;
//     cin >> n >> m >> q;
//     vector<vector<int>> arr(n+1, vector<int>(m+1));
//     for(int i = 1; i <= n; i++)
//         for(int j = 1; j <= m; j++)
//             cin >> arr[i][j];
    
//     //2.求二维前缀和
//     vector<vector<long long>> dp(n+1, vector<long long>(m+1));
//     for(int i = 1; i <= n; i++)
//         for(int j = 1; j <= m; j++)
//             dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];
    
//     int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
//     while(q--)
//     {
//         cin >> x1 >> y1 >> x2 >> y2;
//         cout << dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] <<endl;
//     }
//     return 0;
// }


//560
// class Solution {
// public:
//     int subarraySum(vector<int>& nums, int k) {
//         unordered_map<int, int> hash;
//         hash[0] = 1;
//         int sum = 0, ret = 0;
//         for(int i = 0; i < nums.size(); i++)
//         {
//             sum = sum + nums[i];
//             ret += hash[sum - k];
//             hash[sum]++;
//         }
//         return ret;
//     }
// };

//525.
// class Solution {
// public:
//     // int findMaxLength(vector<int>& nums) {
//     //     unordered_map<int, int> hash;
//     //     int count0 = 0, count1 = 0, ret = 0;
//     //     hash[0] = -1;
//     //     for(int i = 0; i < nums.size(); i++)
//     //     {
//     //         nums[i] == 0 ? ++count0 : ++count1;
//     //         if(hash.count(count0 - count1))//存在才更新
//     //             ret = max(ret, i - hash[count0 - count1]);
//     //         else//不存在, 才保存坐标
//     //             hash[count0 - count1] = i;
//     //     }
//     //     return ret;
//     // } 
//     int findMaxLength(vector<int>& nums) 
//     {
//         unordered_map<int, int> hash;//<sum, position>
//         hash[0] = -1;
//         //将0变成-1, 问题转化为：找出和为0的最长连续子数组
//         int sum = 0, ret = 0;
//         for(int i = 0; i < nums.size(); i++)
//         {
//             sum += nums[i] == 0 ? -1 : 1;
//             if(!hash.count(sum)) hash[sum] = i; 
//             else ret = max(ret, i - hash[sum]);
//         }        
//         return ret;
//     }
// };

//1314.
// class Solution {
// public:
//     vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
//         //1.求dp
//         int n = mat.size(), m = mat[0].size();
//         vector<vector<int>> dp(n+1, vector<int>(m+1)), answer(mat);
//         for(int i = 1; i <= n; i++)
//             for(int j = 1; j <= m; j++)
//                 dp[i][j] = mat[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];

//         //2.在构成的区域中求和
//         for(int i = 1; i <= n; i++)
//         {
//             for(int j = 1; j <= m; j++)
//             {
//                 //处理边界情况
//                 int x1 = max(i-k, 1), y1 = max(j-k, 1);//左上角坐标
//                 int x2 = min(i+k, n), y2 = min(j+k, m);//右下角坐标
//                 //求和
//                 answer[i-1][j-1] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
//             }
//         }
//         return answer;
//     }
// };